//file: LinkedListQueue.java
//This class is to define the Queue ADT using a Linked List approach

import java.util.*;

public class LinkedListQueue
{
	private Node rear;  // points to the rear (tail) element
	private Node head;


	// construct an empty queue using an empty linked list with a dummy header
	public LinkedListQueue()
	{
		head = new Node(null, null);
		rear = head;
	}

	// return true if queue is empty
	public boolean isEmpty()
	{
		return (head.getData() == null);
	}

	// return front element of the queue, but do not remove it
	public Object getFront()
	{
		if (isEmpty())
			throw new NoSuchElementException
			("Can't getFront -- the queue is empty");
		return head.getData();
	}


	// return rear element of the queue, but do not remove it
	public Object getRear()
	{
		if (isEmpty())
			throw new NoSuchElementException
			("Can't getRear -- the queue is empty");
		return rear.getData();
	}

	// enqueue a new element into the rear
	public void enQueue(Object o)
	{
		// check if queue is empty
		if(this.isEmpty())
		{
			this.rear.setData(o);
		}else{

		// this is not empty so add new node and put data in the new node
		Node node = new Node(null,o);

		// set link from former rear node to new rear node
		rear.setLink(node);

		// change rear pointer to the new node
		rear = node;  	  	
		}
	}
		
	// return and remove the front element from the queue
	public Object deQueue()
	{
		// head equals the link from the current
		// node then change the head to the linked node
		//return Object;
		Node temp = new Node(null, head.getData());
		
		// if list is empty
		if(this.isEmpty())
			// Error message or return null???
			return null;// or ThrowException???
		// if list is not empty but has only one node
		// return data, but do not delete the node
		if (head == rear && head.getData() != null)
		{
			// I don't think this is any different than if there are lots of nodes.
			head.setData(null);
			return temp.getData();
		}
		// the queue is not empty and there is more than one node
		head = head.getLink();
		return temp.getData();
	}

	// inner class Node for Linked List
	private class Node
	{
		private Node link;          // Reference to next cell.
		private Object data;        // Reference to data object.

		// The following constructor creates a node with fields
		// initialized as specified by the two parameters.
		public Node(Node n, Object o)
		{
			link = n;
			data = o;
		}

		public Node getLink()
		// POST:  returns a reference to the cell following the
		//     current one.
		{
			return link;
		}

		public Object getData()
		// POST:  returns a reference to the data object for
		//     the current cell. 
		{
			return data;  
		}

		// Mutator methods follow.
		public void setLink(Node n)
		// PRE:  "n" is a new node.
		// POST:  "link" is set to the value of the parameter.
		{
			link = n;
		}

		public void setData(Object o)
		// PRE:  "o" is the new data value for the current node.
		// POST:  "data" is set to the value of the parameter.
		{
			data = o;
		}
	}	    
}	
